package common;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TreeNodeUtils {

    /**
     * 获取二叉树节点
     *
     * @param val
     * @return
     */
    public static <T> TreeNode createTreeNode(int... val) {
        if (val.length == 0) {
            return null;
        }
        int i = 0;
        TreeNode head = null;
        while (i <= 2) {
            int v = val[i++];
            if (head == null) {
                head = new TreeNode(v);
            } else {
                if (head.left == null) {
                    head.left = new TreeNode(v);
                } else {
                    head.right = new TreeNode(v);
                }
            }

        }
        return head;
    }

    public static <T> TreeNode[] getTreeNodes(int... val) {
        if (val.length == 0) {
            return null;
        }
        TreeNode[] treeNodes = new TreeNode[val.length];
        for (int i = 0; i < val.length; i++) {
            treeNodes[i] = new TreeNode(val[i]);
        }
        return treeNodes;
    }

    public static TreeNode getTreeNode() {
        /**
         *            1
         *          /  \
         *         2    3
         *        /\   / \
         *       4 5   6  7
         *        /   / \
         *       8   9  10
         *
         * pre: 1 2 4 5 8 3 6 9 10 7
         */
        TreeNode treeNode1 = TreeNodeUtils.createTreeNode(1, 2, 3);
        TreeNode left = treeNode1.left;
        TreeNode right = treeNode1.right;
        TreeNode[] t3 = TreeNodeUtils.getTreeNodes(4, 5, 6, 7);
        TreeNode[] t4 = TreeNodeUtils.getTreeNodes(8, 9, 10);

        left.left = t3[0];
        left.right = t3[1];
        right.left = t3[2];
        right.right = t3[3];

        t3[1].left = t4[0];
        t3[2].left = t4[1];
        t3[2].right = t4[2];
        return treeNode1;
    }

    /**
     * 镜像树
     * *       1
     * *     2  2
     * *   3 4 4 3
     * *
     */
    public static TreeNode getMirrors() {
        TreeNode treeNode = TreeNodeUtils.createTreeNode(1, 2, 2);
        TreeNode[] treeNodes = TreeNodeUtils.getTreeNodes(3, 4, 4, 3);
        TreeNode left = treeNode.left;
        TreeNode right = treeNode.right;
        left.left = treeNodes[0];
        left.right = treeNodes[1];
        right.left = treeNodes[2];
        right.right = treeNodes[3];
        return treeNode;
    }

    /**
     * 返回搜索二叉树
     *
     * @return
     */
    public static TreeNode getBinarySearchTree() {
        // 1 2 3 4 5 6 7 8 9 10
        /**
         *       5
         *     /   \
         *    3     8
         *   2 4   7 9
         *  1     6   10
         */

        TreeNode root = TreeNodeUtils.createTreeNode(5, 3, 8);
        TreeNode[] thr = TreeNodeUtils.getTreeNodes(2, 4, 7, 9);
        TreeNode[] foth = TreeNodeUtils.getTreeNodes(1, 6, 10);

        thr[0].left = foth[0];
        thr[2].left = foth[1];
        thr[3].right = foth[2];
        root.left.left = thr[0];
        root.left.right = thr[1];
        root.right.left = thr[2];
        root.right.right = thr[3];
        return root;
    }

    /**
     * 返回一棵完全二叉树
     *
     * @return
     */
    public static TreeNode getCBT() {
        // 1 2 3 4 5 6 7 8 9 10
        /**
         *       5
         *     /   \
         *    3     8
         *   2 4   7 9
         *  1
         */

        TreeNode root = TreeNodeUtils.createTreeNode(5, 3, 8);
        TreeNode[] thr = TreeNodeUtils.getTreeNodes(2, 4, 7, 9);
        TreeNode[] foth = TreeNodeUtils.getTreeNodes(1);

        thr[0].left = foth[0];
        root.left.left = thr[0];
        root.left.right = thr[1];
        root.right.left = thr[2];
        root.right.right = thr[3];
        return root;
    }

    // 非平衡二叉树

    /**
     * *                                                        v10v
     * *                                         v6v
     * *                        v3v
     * *                                                          v9v
     * *                                         ^5^
     * *       H1H
     * *                                                          v8v
     * *                                                                          ^12^
     * *                                         v4v
     * *                                                                          v11v
     * *                                                          ^7^
     * *                        ^2^
     * *
     */
    public static TreeNode getNoBalanceTree() {
        TreeNode root = TreeNodeUtils.createTreeNode(1, 2, 3);
        TreeNode[] thr = TreeNodeUtils.getTreeNodes(4, 5, 6);
        TreeNode[] foth = TreeNodeUtils.getTreeNodes(7, 8, 9, 10);
        TreeNode[] fiv = TreeNodeUtils.getTreeNodes(11, 12);

        foth[0].right = fiv[0];
        foth[1].left = fiv[1];

        thr[0].left = foth[0];
        thr[0].right = foth[1];

        thr[1].right = foth[2];
        thr[2].right = foth[3];

        root.left.right = thr[0];
        root.right.left = thr[1];
        root.right.right = thr[2];
        return root;
    }

    private static void printTreeN(TreeNode treeNode) {
        if (treeNode == null) return;
        List<List<Integer>> ans = new ArrayList();
        Queue<TreeNode> queue = new LinkedList();
        queue.add(treeNode);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while (size-- > 0) {
                TreeNode poll = queue.poll();
                list.add(poll.val);
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
            }
            ans.add(list);
        }
        System.out.println(ans);
    }

    public static void printTree(TreeNode node) {
        System.out.println("Binary Tree:");
        printInOrder(node, 0, "H", 17);
    }

    private static void printInOrder(TreeNode head, int high, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, high + 1, "v", len);
        String val = to + head.val + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(high * len) + val);
        printInOrder(head.left, high + 1, "^", len);
    }

    private static String getSpace(int num) {
        String space = " ";
        StringBuilder buf = new StringBuilder();
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }
}
